Relational and object-relational database management systems store information in tables of rows in a database. To retrieve data, queries that request data are submitted to a database server, which computes the queries and returns the data requested.
Query statements submitted to the database server should conform to the syntactical rules of a particular query language. One popular query language, known as the Structured Query Language (SQL), provides users a variety of ways to specify information to be retrieved.
A query submitted to a database server is evaluated by a query optimizer. Based on the evaluation, the query optimizer generates an execution plan optimized for efficient execution. The optimized execution plan may be based on a rewrite of the query.
In one type of inefficient queries, the queries contains logically unnecessary join operations which involve extraneous tables. This type of inefficient queries occur for many reasons. The first reason is that database users often do not write queries directly, but rather utilize “middleware” software programs. Such middleware software programs receive declarative input from the user and automatically generate queries based on the declarative input. Often, the “middleware” software does not check whether the code it generates contains unnecessary join operations. In addition, even a human application developer may introduce unnecessary joins that do not serve any logical purpose because he is not aware of the entirety of the intricacies of query optimization.
Unnecessary joins are undesirable because join operations are expensive operations for a database system to execute. Therefore, it is desirable to develop techniques for rewriting queries to eliminate tables from queries by removing join operations in the queries which contain the tables when such removals have no logical impact on the query results. Table elimination is also referred to as join elimination.
More specifically, there is a need for techniques and mechanisms for optimizing queries by recognizing unnecessary semi-joins, anti-joins, and outer-joins, to remove these unnecessary joins, and to thereby eliminate extraneous tables from database queries.
The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.